package 力扣;

public class Leedcode1524和为奇数的子数组数目 {
    /**
     * 传入一个数组得长度，就可以知道数组得左右奇数和得组合个数
     * @param arr
     * @return
     */
    public int numOfSubarrays(int[] arr){
        final int N = (int) (Math.pow(10,9) + 7);
        int J = 1;//初始化奇数的个数为1;如果全为偶数，奇数J就不会参与res结果的运算，返回的结果也是0；
        int O = 0;//将偶数的组合个数记为0，是偶数就不会res + O = res；
        int res = 0;//结果的暂存变量
        int sum = 0;//数组的各位求和
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum % 2 == 0){//为偶数
                res = (res + O) % N;//为偶数res + 偶数（初始为0）
            }else {//为奇数，J初始为1，和为奇数的组合个数+1；
                res = (res + J) % N;
            }
            if (sum % 2 == 0){//s说明此时的排列组合为偶数，让奇数加一，如果后面在出现一个奇数，那么跟这个新出现的奇数的组合的偶数就刚好有J个
                J++;
            }else {//不是奇数，则是偶数，偶数与之前的奇数组合刚好就是O个
                O++;
            }
        }
        return res;
    }

    public int numOfSubarrays1(int[] arr) {
        final int MODULO = 1000000007;
        int odd = 0, even = 1;
        int subarrays = 0;
        int sum = 0;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            sum += arr[i];
            subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;
            if (sum % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return subarrays;
    }

    public static void main(String[] args) {
        Leedcode1524和为奇数的子数组数目 o = new Leedcode1524和为奇数的子数组数目();
        int[] arr = {2,2,1,1};
        System.out.println(o.numOfSubarrays(arr));
    }
}
